<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE html
  PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xml:lang="zh" lang="zh">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8"/>
<meta name="DC.Type" content="concept"/>
<meta name="DC.Title" content="如何对索引进行搜索"/>
<meta name="DC.subject" content="Apache, Lucene, 原理, 代码, OSSEZ, OSS 计算技术"/>
<meta name="keywords" content="Apache, Lucene, 原理, 代码, OSSEZ, OSS 计算技术"/>
<meta name="DC.Relation" scheme="URI" content="../../tasks/chapter01/chapter01.html"/>
<meta name="prodname" content="Lucene 指南"/>
<meta name="version" content="1.0.0.0"/>
<meta name="brand" content="OSSEZ APACHE LUCENE"/>
<meta name="copyright" content="OSSEZ (中国) 信息技术有限公司 2006, 2012" type="primary"/>
<meta name="DC.Rights.Owner" content="OSSEZ (中国) 信息技术有限公司 2006, 2012" type="primary"/>
<meta name="DC.Format" content="XHTML"/>
<meta name="DC.Identifier" content="chapter01"/>
<meta name="DC.Language" content="zh"/>
<link rel="stylesheet" type="text/css" href="../../css/commonltr.css"/>
<link rel="stylesheet" type="text/css" href="../../css/public.css"/>
<title>如何对索引进行搜索</title>
<svg:script xmlns:syntaxdiagram-svg="http://www.moldflow.com/2006/syntaxdiagram-svg" xmlns="http://www.w3.org/1999/xhtml" xmlns:svg="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" type="text/ecmascript" xlink:href="../../js/constants.js"/><svg:script xmlns:syntaxdiagram-svg="http://www.moldflow.com/2006/syntaxdiagram-svg" xmlns="http://www.w3.org/1999/xhtml" xmlns:svg="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" type="text/ecmascript" xlink:href="../../js/diagram.js"/><svg:script xmlns:syntaxdiagram-svg="http://www.moldflow.com/2006/syntaxdiagram-svg" xmlns="http://www.w3.org/1999/xhtml" xmlns:svg="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" type="text/ecmascript" xlink:href="../../js/sequence.js"/><svg:script xmlns:syntaxdiagram-svg="http://www.moldflow.com/2006/syntaxdiagram-svg" xmlns="http://www.w3.org/1999/xhtml" xmlns:svg="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" type="text/ecmascript" xlink:href="../../js/loop.js"/><svg:script xmlns:syntaxdiagram-svg="http://www.moldflow.com/2006/syntaxdiagram-svg" xmlns="http://www.w3.org/1999/xhtml" xmlns:svg="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" type="text/ecmascript" xlink:href="../../js/decision.js"/><svg:script xmlns:syntaxdiagram-svg="http://www.moldflow.com/2006/syntaxdiagram-svg" xmlns="http://www.w3.org/1999/xhtml" xmlns:svg="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" type="text/ecmascript" xlink:href="../../js/revdecision.js"/><svg:script xmlns:syntaxdiagram-svg="http://www.moldflow.com/2006/syntaxdiagram-svg" xmlns="http://www.w3.org/1999/xhtml" xmlns:svg="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" type="text/ecmascript" xlink:href="../../js/boxed.js"/><svg:script xmlns:syntaxdiagram-svg="http://www.moldflow.com/2006/syntaxdiagram-svg" xmlns="http://www.w3.org/1999/xhtml" xmlns:svg="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" type="text/ecmascript" xlink:href="../../js/unboxed.js"/><svg:script xmlns:syntaxdiagram-svg="http://www.moldflow.com/2006/syntaxdiagram-svg" xmlns="http://www.w3.org/1999/xhtml" xmlns:svg="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" type="text/ecmascript" xlink:href="../../js/text.js"/><svg:script xmlns:syntaxdiagram-svg="http://www.moldflow.com/2006/syntaxdiagram-svg" xmlns="http://www.w3.org/1999/xhtml" xmlns:svg="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" type="text/ecmascript" xlink:href="../../js/void.js"/><svg:script xmlns:syntaxdiagram-svg="http://www.moldflow.com/2006/syntaxdiagram-svg" xmlns="http://www.w3.org/1999/xhtml" xmlns:svg="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" type="text/ecmascript" xlink:href="../../js/notecontainer.js"/><svg:script xmlns:syntaxdiagram-svg="http://www.moldflow.com/2006/syntaxdiagram-svg" xmlns="http://www.w3.org/1999/xhtml" xmlns:svg="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" type="text/ecmascript" xlink:href="../../js/note.js"/><svg:script xmlns:syntaxdiagram-svg="http://www.moldflow.com/2006/syntaxdiagram-svg" xmlns="http://www.w3.org/1999/xhtml" xmlns:svg="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" type="text/ecmascript" xlink:href="../../js/main.js"/><link rel="stylesheet" type="text/css" href="css/syntaxdiagram.css"/></head>
<body id="chapter01">


  <h1 class="title topictitle1">如何对索引进行搜索</h1>

  
  <div class="body conbody">
    <p class="p">到这里似乎我们可以宣布“我们找到想要的文档了”。</p>

    <p class="p">然而事情并没有结束，找到了仅仅是全文检索的一个方面。</p>

    <p class="p">不是吗？如果仅仅只有一个或十个文档包含我们查询的字符串，我们的确找到了。</p>

    <p class="p">然而如果结果有一千个，甚至成千上万个呢？那个又是您最想要的文件呢？</p>

    <p class="p">打开Google 吧，比如说您想在微软找份工作，于是您输入“ossez”，您却发现总共有 370,000 个结果返回。</p>

    <p class="p">好大的数字呀，突然发现找不到是一个问题，找到的太多也是一个问题。</p>

    <p class="p">在如此多的结果中，如何将最相关的放在最前面呢？</p>

    <p class="p"><img class="image" src="../../images/chapter01_03_01.png" alt="OSSEZ 搜索结果表"/></p>

    <p class="p">当然 Google 做的很不错，您一下就找到了 ossez。</p>

    <p class="p">想象一下，如果前几个全部是“OSS 计算技术 ”将是多么可怕的事情呀。</p>

    <p class="p">如何像Google 一样，在成千上万的搜索结果中，找到和查询语句最相关的呢？</p>

    <p class="p">如何判断搜索出的文档和查询语句的相关性呢？</p>

    <p class="p">这要回到我们第三个问题：如何对索引进行搜索？</p>

    <p class="p">搜索主要分为以下几步：</p>

    <div class="section"><h2 class="title sectiontitle">用户输入查询语句</h2>
      
      <p class="p">查询语句同我们普通的语言一样，也是有一定语法的。</p>

      <p class="p">不同的查询语句有不同的语法，如SQL 语句就有一定的语法。</p>

      <p class="p">查询语句的语法根据全文检索系统的实现而不同。最基本的有比如：AND, OR, NOT 等。</p>

      <p class="p">举个例子，用户输入语句：lucene AND learned NOT hadoop。</p>

      <p class="p">说明用户想找一个包含lucene 和learned 然而不包括hadoop 的文档。</p>

    </div>

    <div class="section"><h2 class="title sectiontitle">对查询语句进行词法分析，语法分析，及语言处理</h2>
      
      <p class="p">由于查询语句有语法，因而也要进行语法分析，语法分析及语言处理。</p>

      <div class="p"><ol class="ol">
          <li class="li">
            <p class="p">词法分析主要用来识别单词和关键字</p>

            <p class="p">如上述例子中，经过词法分析，得到单词有lucene，learned，hadoop, 关键字有 AND, NOT。</p>

            <p class="p">如果在词法分析中发现不合法的关键字，则会出现错误。</p>

            <p class="p">如lucene AMD learned，其中由于AND 拼错，导致AMD 作为一个普通的单词参与查询。</p>

          </li>

          <li class="li">
            <p class="p">语法分析主要是根据查询语句的语法规则来形成一棵语法树</p>

            <p class="p">如果发现查询语句不满足语法规则，则会报错。如lucene NOT AND learned，则会出错。</p>

            <p class="p">如上述例子，lucene AND learned NOT hadoop 形成的语法树如下：</p>

            <p class="p"><img class="image" src="../../images/chapter01_03_02.png" alt="语法树"/></p>

          </li>

          <li class="li">
            <p class="p">语言处理同索引过程中的语言处理几乎相同</p>

            <p class="p">如learned 变成learn 等。</p>

            <p class="p">经过第二步，我们得到一棵经过语言处理的语法树。</p>

            <p class="p"><img class="image" src="../../images/chapter01_03_03.png"/></p>

          </li>

        </ol>
</div>

    </div>

    <div class="section"><h2 class="title sectiontitle">搜索索引，得到符合语法树的文档</h2>
      
      <p class="p">此步骤有分几小步：</p>

      <div class="p"><ol class="ol">
          <li class="li">首先，在反向索引表中，分别找出包含lucene，learn，hadoop 的文档链表。</li>

          <li class="li">其次，对包含lucene，learn 的链表进行合并操作，得到既包含lucene 又包含learn 的文档链表。</li>

          <li class="li">然后，将此链表与hadoop 的文档链表进行差操作，去除包含hadoop 的文档，从而得到既包含lucene 又包含learn 而且不包含hadoop 的文档链表。</li>

          <li class="li">此文档链表就是我们要找的文档。</li>

        </ol>
</div>

    </div>

    <div class="section"><h2 class="title sectiontitle">根据得到的文档和查询语句的相关性，对结果进行排序</h2>
      
      <p class="p">虽然在上一步，我们得到了想要的文档，然而对于查询结果应该按照与查询语句的相关性进行排序，越相关者越靠前。</p>

      <p class="p">如何计算文档和查询语句的相关性呢？</p>

      <p class="p">不如我们把查询语句看作一片短小的文档，对文档与文档之间的相关性(relevance)进行打分(scoring)，分数高的相关性好，就应该排在前面。</p>

      <p class="p">那么又怎么对文档之间的关系进行打分呢？</p>

      <p class="p">这可不是一件容易的事情，首先我们看一看判断人之间的关系吧。</p>

      <p class="p">首先看一个人，往往有很多要素，如性格，信仰，爱好，衣着，高矮，胖瘦等等。</p>

      <p class="p">其次对于人与人之间的关系，不同的要素重要性不同，性格，信仰，爱好可能重要些，衣着，高矮，胖瘦可能就不那么重要了，所以具有相同或相似性格，信仰，爱好的人比较容易成为好的朋友，然而衣着，高矮，胖瘦不同的人，也可以成为好的朋友。</p>

      <p class="p">因而判断人与人之间的关系，首先要找出哪些要素对人与人之间的关系最重要，比如性格，信仰，爱好。其次要判断两个人的这些要素之间的关系，比如一个人性格开朗，另一个人性格外向，一个人信仰佛教，另一个信仰上帝，一个人爱好打篮球，另一个爱好踢足球。我们发现，两个人在性格方面都很积极，信仰方面都很善良，爱好方面都爱运动，因而两个人关系应该会很好。</p>

      <p class="p">我们再来看看公司之间的关系吧。</p>

      <p class="p">首先看一个公司，有很多人组成，如总经理，经理，首席技术官，普通员工，保安，门卫等。</p>

      <p class="p">其次对于公司与公司之间的关系，不同的人重要性不同，总经理，经理，首席技术官可能更重要一些，普通员工，保安，门卫可能较不重要一点。所以如果两个公司总经理，经理，首席技术官之间关系比较好，两个公司容易有比较好的关系。然而一位普通员工就算与另一家公司的一位普通员工有血海深仇，怕也难影响两个公司之间的关系。</p>

      <p class="p">因而判断公司与公司之间的关系，首先要找出哪些人对公司与公司之间的关系最重要，比如总经理，经理，首席技术官。其次要判断这些人之间的关系，不如两家公司的总经理曾经是同学，经理是老乡，首席技术官曾是创业伙伴。我们发现，两家公司无论总经理，经理，首席技术官，关系都很好，因而两家公司关系应该会很好。</p>

      <p class="p">分析了两种关系，下面看一下如何判断文档之间的关系了。</p>

      <p class="p">首先，一个文档有很多词(Term)组成，如search, lucene, full-text, this, a, what等。</p>

      <p class="p">其次对于文档之间的关系，不同的Term重要性不同，比如对于本篇文档，search, Lucene,full-text 就相对重要一些，this, a , what 可能相对不重要一些。所以如果两篇文档都包含search,Lucene，fulltext，这两篇文档的相关性好一些，然而就算一篇文档包含this, a, what，另一篇文档不包含this, a, what，也不能影响两篇文档的相关性。</p>

      <p class="p">因而判断文档之间的关系，首先找出哪些词(Term)对文档之间的关系最重要，如search, Lucene, fulltext。然后判断这些词(Term)之间的关系。</p>

      <p class="p">找出词(Term)对文档的重要性的过程称为计算词的权重(Term weight)的过程。</p>

      <p class="p">计算词的权重(term weight)有两个参数，第一个是词(Term)，第二个是文档(Document)。</p>

      <p class="p">词的权重(Term weight)表示此词(Term)在此文档中的重要程度，越重要的词(Term)有越大的权重(Term weight)，因而在计算文档之间的相关性中将发挥更大的作用。</p>

      <p class="p">判断词(Term)之间的关系从而得到文档相关性的过程应用一种叫做向量空间模型的算法(Vector Space Model)。</p>

      <p class="p">下面仔细分析一下这两个过程：</p>

      <div class="p"><ol class="ol">
          <li class="li">
            <p class="p">计算权重(Term weight)的过程</p>

            <div class="p"><ul class="ul">
                <li class="li">
                  <p class="p">Term Frequency (tf)：即此Term 在此文档中出现了多少次。</p>

                  <p class="p">tf 越大说明越重要。</p>

                </li>

                <li class="li">
                  <p class="p">Document Frequency (df)：即有多少文档包含次Term。</p>

                  <p class="p">df 越大说明越不重要。</p>

                </li>

              </ul>
</div>

            <p class="p">词(Term)在文档中出现的次数越多，说明此词(Term)对该文档越重要，如“搜索”这个词，在本文档中出现的次数很多，说明本文档主要就是讲这方面的事的。</p>

            <p class="p">然而在一篇英语文档中，this 出现的次数更多，就说明越重要吗？不是的，这是由第二个因素进行调整，第二个因素说明，有越多的文档包含此词(Term), 说明此词(Term)太普通，不足以区分这些文档，因而重要性越低。</p>

            <p class="p">这也如我们程序员所学的技术，对于程序员本身来说，这项技术掌握越深越好（掌握越深说明花时间看的越多，tf 越大），找工作时越有竞争力。</p>

            <p class="p">然而对于所有程序员来说，这项技术懂得的人越少越好（懂得的人少df 小），找工作越有竞争力。</p>

            <p class="p">人的价值在于不可替代性就是这个道理。</p>

          </li>

          <li class="li">
            <p class="p">判断Term 之间的关系从而得到文档相关性的过程，也即
向量空间模型的算法(VSM)。</p>

            <p class="p">我们把文档看作一系列词(Term)，每一个词(Term)都有一个权重(Term weight)，不同的词(Term)根据自己在文档中的权重来影响文档相关性的打分计算。</p>

            <p class="p">于是我们把所有此文档中词(term)的权重(term weight) 看作一个向量。</p>

            <div class="p"><pre class="pre codeblock">Document = {term1, term2, …… ,term N}

Document Vector = {weight1, weight2, …… ,weight N}
</pre>
</div>

            <p class="p">同样我们把查询语句看作一个简单的文档，也用向量来表示。</p>

            <div class="p"><pre class="pre codeblock">Query = {term1, term 2, …… , term N}

Query Vector = {weight1, weight2, …… , weight N}</pre>
</div>

            <p class="p">我们把所有搜索出的文档向量及查询向量放到一个N 维空间中，每个词(term)是一维。</p>

            <p class="p"><img class="image" src="../../images/chapter01_03_04.png" alt="向量模型"/></p>

            <p class="p">我们认为两个向量之间的夹角越小，相关性越大。</p>

            <p class="p">所以我们计算夹角的余弦值作为相关性的打分，夹角越小，余弦值越大，打分越高，相关性越大。</p>

            <p class="p">有人可能会问，查询语句一般是很短的，包含的词(Term)是很少的，因而查询向量的维数很小，而文档很长，包含词(Term)很多，文档向量维数很大。你的图中两者维数怎么都是N 呢？</p>

            <p class="p">在这里，既然要放到相同的向量空间，自然维数是相同的，不同时，取二者的并集，如果不含某个词(Term)时，则权重(Term Weight)为0。</p>

            <p class="p">相关性打分公式如下：</p>

            <p class="p"><img class="image" src="../../images/chapter01_03_05.png" alt="相关性算法"/></p>

            <p class="p">说了这么多，其实还没有进入到Lucene，而仅仅是信息检索技术(Information retrieval)中的基本理论，然而当我们看过Lucene 后我们会发现，Lucene 是对这种基本理论的一种基本的的实践。</p>

            <p class="p">所以在以后分析Lucene 的文章中，会常常看到以上理论在Lucene 中的应用。</p>

            <p class="p">在进入Lucene 之前，对上述索引创建和搜索过程所一个总结：</p>

            <p class="p"><img class="image" src="../../images/chapter01_03_06.png" alt="Lucene 总结"/></p>

          </li>

        </ol>
</div>

    </div>

    <div class="section"><h2 class="title sectiontitle">Lucene 架构</h2>
      
      <p class="p">索引过程：</p>

      <div class="p"><ol class="ol">
          <li class="li">有一系列被索引文件</li>

          <li class="li">被索引文件经过语法分析和语言处理形成一系列词(Term)。</li>

          <li class="li">经过索引创建形成词典和反向索引表。</li>

          <li class="li">通过索引存储将索引写入硬盘。</li>

        </ol>
</div>

      <p class="p">搜索过程：</p>

      <div class="p"><ol class="ol">
          <li class="li">用户输入查询语句。</li>

          <li class="li">对查询语句经过语法分析和语言分析得到一系列词(Term)。</li>

          <li class="li">通过语法分析得到一个查询树。</li>

          <li class="li">通过索引存储将索引读入到内存。</li>

          <li class="li">利用查询树搜索索引，从而得到每个词(Term)的文档链表，对文档链表进行交，差，并得到结果文档。</li>

          <li class="li">将搜索到的结果文档对查询的相关性进行排序。</li>

          <li class="li">返回查询结果给用户。</li>

        </ol>
</div>

    </div>

    <div class="section">
      <a class="xref" href="http://www.ossez.com/forum.php?mod=viewthread&amp;tid=18382&amp;fromuid=426" target="_blank">http://www.ossez.com/forum.php?mod=viewthread&amp;tid=18382&amp;fromuid=426</a>
    </div>

  </div>

<div class="related-links">
<div class="familylinks">
<div class="parentlink"><strong>父主题：</strong> <a class="link" href="../../tasks/chapter01/chapter01.html">基本原理</a></div>
</div>
</div>

</body>
</html>